package _11_整理题目._6_模拟设计._计算器;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 *
 *
 */
public class _02_计算器_带小括号 {
    // 计算器
    public int calculate(String s) {
        return calRPN(getRPN(s));
    }

    // 中缀转后缀
    public List<String> getRPN(String s) {
        String str = s.replaceAll(" ", "");
        int n = str.length();

        Stack<String> stack = new Stack<>();
        List<String> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (Character.isDigit(str.charAt(i))) {
                int num = 0;
                while (i < n && Character.isDigit(str.charAt(i))) {
                    num = num  * 10 + (str.charAt(i)-'0');
                    i++;
                }
                i--; // 往回走一步
                list.add(num + "");
            } else if (str.charAt(i) == '(') {
                stack.push("(");
            } else if (str.charAt(i) == ')') {
                while (!stack.isEmpty() && !stack.peek().equals("(")) {
                    list.add(stack.pop());
                }
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                while (!stack.isEmpty() && !stack.peek().equals("(") && getPri(str.charAt(i)+"") <= getPri(stack.peek())) {
                    list.add(stack.pop());
                }
                stack.push(str.charAt(i)+"");
            }
        }

        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }

    public int getPri(String str) {
        if (str.equals("+") || str.equals("-")) return 1;
        if (str.equals("*") || str.equals("/")) return 2;
        return -1;
    }

    // 后缀求解
    public int calRPN(List<String> list) {
        Stack<Integer> stack = new Stack<>();
        for (String str : list) {
            if (str.matches("\\d+")) {
                stack.push(Integer.valueOf(str));
            } else {
                int a = stack.isEmpty() ? 0 : stack.pop();
                int b = stack.isEmpty() ? 0 : stack.pop();
                if (str.equals("+")) stack.push(b + a);
                else if (str.equals("-")) stack.push(b - a);
                else if (str.equals("*")) stack.push(b * a);
                else if (str.equals("/")) stack.push(b / a);
            }
        }
        return stack.pop();
    }

    @Test
    public void main() {
        String s = "2*(5+5*2)/3+(6/2+8)";
        System.out.println(calculate(s));// 21
    }
}
